#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int& prei,
        int inbegin, int inend) {
        if (inbegin > inend)
            return nullptr;

        TreeNode* root = new TreeNode(preorder[prei]);

        int rooti = 0;
        while (rooti <= inend) {
            if (inorder[rooti] == preorder[prei])
                break;
            else
                rooti++;
        }
        prei++;
        root->left = buildTree(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = buildTree(preorder, inorder, prei, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};